/*
 * @Author: szx
 * @Date: 2021-12-12 19:55:11
 * @LastEditTime: 2021-12-12 20:09:01
 * @Description:
 * @FilePath: \leetcode\200-299\239\239.js
 */
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
    const n = nums.length;
    const res = [];
    // 这就是deque，双向队列了属于是，既要后面弹出来，也要前面shift
    const q = [];
    for (let i = 0; i < n; i++) {
        // 如果当前的数字比最后一个数字大，那么不断弹出，直至找到比他小的。
        while (q.length && nums[i] >= nums[q[q.length - 1]]) {
            q.pop();
        }
        q.push(i);
        // 判断当前最大值（即队首元素）是否在窗口中，若不在便将其出队
        if (q[0] <= i - k) {
            q.shift();
        }
        // 当达到窗口大小时便开始向结果中添加数据
        if (i >= k - 1) res.push(nums[q[0]]);
    }
    return res;
};
console.log(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3));
